package top100;

/**
 * 704. 二分查找
 *
 * @see <a href="https://leetcode.cn/problems/binary-search/>binary-search</a>
 */
public class _0704_binary_search
{
    /**
     * 二分查找
     *
     * 在升序数组 nums  中寻找目标值 target ，对于特定下标 i，比较 nums[i] 和 target 的大小：
     *  1. 如果 nums[i]=target，则下标 i 即为要寻找的下标；
     *  2. 如果 nums[i]>target，则 target 只可能在下标 i 的左侧；
     *  3. 如果 nums[i]<target，则 target 只可能在下标 i 的右侧。
     *
     * 时间复杂度：O(log n) ，其中 n 是数组的长度。
     * 空间复杂度：O(1)。
     */
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (nums == null || nums.length == 0
                || nums[0] > target || nums[nums.length - 1] < target) {
            return -1;
        }

        // 左闭右闭区间
        int left = 0;
        int right = nums.length - 1; // 定义target在左闭右闭的区间里，[left, right]
        // 二分查找的条件是查找范围不为空，即 left≤right
        while (left <= right) {  // 当left==right，区间[left, right]依然有效，所以用 <=
            int mid = (left + right) / 2;// 防止溢出

            if (nums[mid] == target) {
                // 数组中找到目标值，直接返回下标
                return mid;
            } else if (nums[mid] > target) {
                // target 在左区间，所以[left, middle - 1]
                right = mid - 1;
            } else if (nums[mid] < target) {
                // target 在右区间，所以[middle + 1, right]
                left = mid + 1;
            }
        }

        return -1;
    }
}
